package com.example.lib5.sort;


import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {-9, 78, 0, -23, -567, 70,89,-55,90,-23,77};
        int[] arr = {12,4,-1,0,2,-23,24};
        System.out.println(Arrays.toString(arr));
        // 5/2=2(都是int类型，后面的会省略),5.5/2=2.75 float类型
        quickSort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序 以中间值作为基点
     * @param arr   要排序的数组
     * @param left  数组的最左边值
     * @param right 数组的最右边值
     */
    private static void quickSort(int[] arr, int left, int right) {
        //获取中间值
        int l = left;
        int r = right;
        int temp = 0;
        int centerValue = arr[(left + right) / 2];
        //l++,r--,l<r表明遍历完了
        while (l < r) {
            //如果左边的值小于中间值得话就不用管它，继续看下一个；如果是大于中间值，那么它就要移动（这里跟右边的值进行交换）
            while (arr[l] < centerValue) {
                l += 1;
            }
            //右边的值大于中间值的话，就不管它，继续看下一个，如果是小于的话，就要标记起来，准备移动（这里跟左边的值进行交换）
            while (arr[r] > centerValue) {
                r -= 1;
            }
            //左边索引>=右边索引，表示都遍历完了，退出
            if (l >= r) {
                break;
            }
            //交换位置
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //需要下面，如果没有下面会一直遍历下去，
            if (arr[l] == centerValue) {
                r -= 1;
            }
            if (arr[r] == centerValue) {//这个表示没换位置时的arr[l]值
                l += 1;
            }
        }
        System.out.println(Arrays.toString(arr));
        if (l == r) {
            l += 1;
            r -= 1;
        }
        if (left < r) {
            quickSort(arr, left, r);
        }
        if (right > l) {
            quickSort(arr, l, right);
        }


    }
    private static void quickSort2(int[] arr, int left, int right) {
        //获取中间值
        int center = arr[left / right];
        int l=left;
        int r=right;
        //以中间值为基准，while循环，将值分到数组两边
        while (l>r) {
            //遍历左边，获取大于center的值，标记(小于的不用改变位置，不操作)
            while (arr[l] < center) {
                l++;
            }
            //遍历右边,获取小于center的值，标记
            while (arr[r] > center) {
                r--;
            }
            //遍历完了退出
            if (l>=r) {
                break;
            }
            //交换位置
            int temp=arr[r];
            arr[r]=arr[l];
            arr[l]=temp;

            //左右两边的值如果=center，表示没移动,但是要要让它退出循环，所以要++，--
            if (arr[l]==center) {
                r--;
            }
            if (arr[r]==center) {
                l++;
            }
        }
        //校正l,r  这里l，r都会靠近中间
        if (l==r){
            l--;
            r++;
        }
        //左右两边遍历
        if (left<l){
            quickSort2(arr,left,l);
        }
        if (r<right){
            quickSort2(arr,r,right);
        }
    }

}
